package jzOffer;

public class Num76 {
    public int findKthLargest(int[] nums, int k) {
        int n=nums.length;
        return quickSort(nums,0,n-1,n-k);
    }
    private int quickSort(int[] nums,int i,int j,int k){
        if(i>j) return -1;
        int p=partition(nums,i,j);
        if(p==k){
            return nums[p];
        }else if(p<k){
            return quickSort(nums,p+1,j,k);
        }else{
            return quickSort(nums,0,p-1,k);
        }
    }

    /**
     * 二路快排
     * @param nums
     * @param l
     * @param r
     * @return
     */
    private int partition(int[] nums,int l,int r){
        int v=nums[l];
        int i=l+1;
        int j=r;
        while(true){
            while(i<=j && nums[i]<v){
                i++;
            }
            while(i<=j && nums[j]>v){
                j--;
            }
            if(i>j) break;
            swap(nums,i,j);
            i++;
            j--;

        }
        swap(nums,l,j);
        return j;
    }
    private void swap(int[] nums,int i,int j){
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
}
